//穷举后不加入所有结果版本
//这个版本将dfs算法改为Folrd-warshall算法
//Yen's算法出错
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath> // for pow

using namespace std;
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <cmath>

using namespace std;

// 使用 Dijkstra 算法计算从 start 到 end 的最短路径
vector<size_t> dijkstra(size_t start, size_t end, const vector<vector<size_t>>& roadlength) {
    size_t N = roadlength.size();
    vector<size_t> dist(N, INT_MAX); // 存储从 start 到各个节点的最短距离
    vector<size_t> parent(N, SIZE_MAX); // 存储最短路径的父节点
    vector<bool> visited(N, false); // 记录节点是否已访问
    dist[start] = 0;

    // 优先队列用于 Dijkstra
    priority_queue<pair<size_t, size_t>, vector<pair<size_t, size_t>>, greater<pair<size_t, size_t>>> pq;
    pq.push({0, start}); // 初始时，将起点加入队列

    while (!pq.empty()) {
        size_t u = pq.top().second;
        size_t d = pq.top().first;
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        // 如果找到了终点，提前结束
        if (u == end) break;

        for (size_t v = 0; v < N; v++) {
            if (roadlength[u][v] != INT_MAX && !visited[v]) { // 仅考虑未访问且有道路的节点
                size_t new_dist = d + roadlength[u][v];
                if (new_dist < dist[v]) {
                    dist[v] = new_dist;
                    parent[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }
    }

    // 从 end 反向推导路径
    vector<size_t> path;
    for (size_t v = end; v != SIZE_MAX; v = parent[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

// 修改后的 Dijkstra，避免已经找到的路径
vector<size_t> dijkstra_with_block(size_t start, size_t end, vector<vector<size_t>>& roadlength, const vector<size_t>& blocked_path) {
    size_t N = roadlength.size();
    vector<size_t> dist(N, INT_MAX);
    vector<size_t> parent(N, SIZE_MAX);
    vector<bool> visited(N, false);
    dist[start] = 0;

    // 遍历阻塞路径
    for (size_t i = 0; i < blocked_path.size() - 1; i++) {
        size_t u = blocked_path[i];
        size_t v = blocked_path[i + 1];
        roadlength[u][v] = INT_MAX; // 阻塞边
        roadlength[v][u] = INT_MAX; // 双向阻塞
    }

    // Dijkstra 算法
    priority_queue<pair<size_t, size_t>, vector<pair<size_t, size_t>>, greater<pair<size_t, size_t>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        size_t u = pq.top().second;
        size_t d = pq.top().first;
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        if (u == end) break;

        for (size_t v = 0; v < N; v++) {
            if (roadlength[u][v] != INT_MAX && !visited[v]) {
                size_t new_dist = d + roadlength[u][v];
                if (new_dist < dist[v]) {
                    dist[v] = new_dist;
                    parent[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }
    }

    // 从 end 反向推导路径
    vector<size_t> path;
    for (size_t v = end; v != SIZE_MAX; v = parent[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());

    return path.empty() || path.front() != start ? vector<size_t>() : path;
}


// Yen's Algorithm，返回从 start 到 end 的 k 条最短路径
vector<vector<size_t>> yen_algorithm(size_t start, size_t end, const vector<vector<size_t>>& roadlength, size_t k) {
    vector<vector<size_t>> k_shortest_paths;
    vector<vector<size_t>> roadlength_modified = roadlength;

    // 第一条最短路径
    vector<size_t> first_path = dijkstra(start, end, roadlength);
    k_shortest_paths.push_back(first_path);

    // 逐步寻找其余的 k-1 条路径
    for (size_t i = 1; i < k; i++) {
        // 逐条修改图的道路
        vector<size_t> candidate_path = dijkstra_with_block(start, end, roadlength_modified, k_shortest_paths[i - 1]);
        if (candidate_path.empty()) break;
        k_shortest_paths.push_back(candidate_path);
    }

    return k_shortest_paths;
}



// 计算路径的总长度
size_t calculatePathLength(const vector<size_t>& path, const vector<vector<size_t>>& roadlength) {
    size_t length = 0;
    for (size_t i = 0; i < path.size() - 1; ++i) {
        length += roadlength[path[i]][path[i+1]];
    }
    return length;
}

// 检测当前车辆路径组合是否会导致堵车
struct Event {
    size_t time;
    size_t u; // 起始节点
    size_t v; // 结束节点
    bool enter; // 进入路段（true）还是离开路段（false）
    // 重载比较运算符，使优先队列按时间升序排列
    bool operator>(const Event& other) const {
        return time > other.time;
    }
};

bool checkTraffic(const vector<vector<size_t>>& combination,
                  const vector<vector<size_t>>& roadlength,
                  const vector<vector<size_t>>& restrictions) {
    // 创建优先队列，存储事件
    priority_queue<Event, vector<Event>, greater<Event>> eventQueue;

    // 初始化事件队列
    for (const vector<size_t>& path : combination) {
        size_t current_time = 0;
        for (size_t i = 1; i < path.size(); ++i) {
            size_t u = path[i - 1];
            size_t v = path[i];
            size_t length = roadlength[u][v];
            eventQueue.push({current_time, u, v, true}); // 进入事件
            eventQueue.push({current_time + length, u, v, false}); // 离开事件
            current_time += length;
        }
    }

    // 维护当前每条道路的流量
    vector<vector<size_t>> current_flow(roadlength.size(), vector<size_t>(roadlength.size(), 0));

    while (!eventQueue.empty()) {
        size_t current_time = eventQueue.top().time;
        vector<Event> same_time_events;
        // 取出所有时间等于current_time的事件
        while (!eventQueue.empty() && eventQueue.top().time == current_time) {
            same_time_events.push_back(eventQueue.top());
            eventQueue.pop();
        }
        // 先处理离开事件
        for (Event& event : same_time_events) {
            if (!event.enter) {
                if (current_flow[event.u][event.v] > 0) {
                    current_flow[event.u][event.v]--;
                    current_flow[event.v][event.u]--;
                }
            }
        }
        // 再处理进入事件
        for (Event& event : same_time_events) {
            if (event.enter) {
                current_flow[event.u][event.v]++;
                current_flow[event.v][event.u]++;
                if (current_flow[event.u][event.v] > restrictions[event.u][event.v]) {
                    return false; // 堵车
                }
            }
        }
    }

    // 所有事件处理完毕，没有堵车
    return true;
}

// 计算当前组合的总路径长度
size_t calculateTotalLength(const vector<vector<size_t>>& combination, const vector<vector<size_t>>& roadlength) {
    size_t total_length = 0;
    for (const vector<size_t>& path : combination) {
        for (size_t i = 1; i < path.size(); i++) {
            size_t u = path[i - 1];
            size_t v = path[i];
            total_length += roadlength[u][v];
        }
    }
    return total_length;
}

// 遍历所有车辆路径组合的函数
void traverseCombinations(const vector<vector<vector<size_t>>>& all_cars_paths, size_t car_index, vector<vector<size_t>>& current_combination, const vector<vector<size_t>>& roadlength, const vector<vector<size_t>>& restrictions, vector<vector<size_t>>& best_combination, size_t& min_total_length) {
    // 如果已经处理完所有车辆，检查当前组合是否最优
    if (car_index == all_cars_paths.size()) {
        if (checkTraffic(current_combination, roadlength, restrictions)) {
            size_t total_length = calculateTotalLength(current_combination, roadlength);
            if (total_length < min_total_length) {
                min_total_length = total_length;
                best_combination = current_combination;
            }
        }
        return;
    }

    // 遍历当前车辆的所有路径方案
    for (const vector<size_t>& path : all_cars_paths[car_index]) {
        current_combination.push_back(path); // 选择当前路径方案
        traverseCombinations(all_cars_paths, car_index + 1, current_combination, roadlength, restrictions, best_combination, min_total_length); // 递归处理下一辆车
        current_combination.pop_back(); // 回溯，撤销选择
    }
}

// 找到不堵车且总路径长度最短的组合
void findBestCombination(const vector<vector<vector<size_t>>>& all_cars_paths, const vector<vector<size_t>>& roadlength, const vector<vector<size_t>>& restrictions) {
    vector<vector<size_t>> best_combination; // 存储最短组合
    size_t min_total_length = INT_MAX; // 记录最短组合的总路径长度

    // 遍历所有车辆路径组合
    vector<vector<size_t>> current_combination;
    traverseCombinations(all_cars_paths, 0, current_combination, roadlength, restrictions, best_combination, min_total_length);

    // 输出最短组合
    if (!best_combination.empty()) {
        cout << "Best combination (total length: " << min_total_length << "):" << endl;
        for (size_t i = 0; i < best_combination.size(); i++) {
            cout << "Car " << i + 1 << " path: ";
            for (size_t node : best_combination[i]) {
                cout << node + 1 << " ";
            }
            cout << endl;
        }
    } else {
        cout << "No valid combination found!" << endl;
    }
}


int main() {
    size_t N, M;
    cin >> N >> M;

    // 动态分配二维数组
    vector<vector<size_t>> roadlength(N, vector<size_t>(N, INT_MAX)); // 存储道路长度
    vector<vector<size_t>> restrictions(N, vector<size_t>(N)); // 存储道路的流量限制
    vector<vector<size_t>> cars(M, vector<size_t>(2)); // 存储每辆车的起点和终点

    // 读取道路长度
    for (size_t i = 0; i < N; i++) {
        for (size_t j = 0; j < N; j++) {
            cin >> roadlength[i][j];
            if (roadlength[i][j] == 0 && i != j) {
                roadlength[i][j] = INT_MAX; // 如果道路长度为 0，则距离为无穷大
            }
        }
    }

    // 读取道路的流量限制
    for (size_t i = 0; i < N; i++) {
        for (size_t j = 0; j < N; j++) {
            cin >> restrictions[i][j];
        }
    }

    // 读取每辆车的起点和终点
    for (size_t i = 0; i < M; i++) {
        cin >> cars[i][0] >> cars[i][1];
        cars[i][0]--; // 将输入的起点和终点转换为从 0 开始的索引
        cars[i][1]--;
    }

    // 计算k的值
    size_t k = (size_t)pow(SIZE_MAX, 1.0 / M);

    // 存储每辆车的前k条最短路径
    vector<vector<vector<size_t>>> all_cars_paths(M);

    // 为每辆车找到前k条最短路径
    for (size_t i = 0; i < M; i++) {
        size_t start = cars[i][0];
        size_t end = cars[i][1];

        vector<vector<size_t>> k_paths = yen_algorithm(start, end, roadlength, k);
        all_cars_paths[i] = k_paths;
        
        cout<<k<<" "<<all_cars_paths[i].size()<<endl;
    }

    // 找到不堵车且总路径长度最短的组合
    findBestCombination(all_cars_paths, roadlength, restrictions);

    return 0;
}